Bound on Global Extremum
Adapted from: SOSTOOLS' SOSDEMO3 (See Section 4.3 of SOSTOOLS User's Manual)
using DynamicPolynomials
@polyvar x1 x2(x1, x2)The Goldstein-Price function $f(x)$ is defined as follows:
f1 = x1 + x2 + 1
f2 = 19 - 14x1 + 3x1^2 - 14x2 + 6x1*x2 + 3x2^2
f3 = 2x1 - 3x2
f4 = 18 - 32x1 + 12x1^2 + 48x2 - 36x1*x2 + 27x2^2
f = (1 + f1^2 * f2) * (30 + f3^2 * f4)\[ 600 + 720x2 + 720x1 + 3060x2^{2} - 4680x1x2 + 1260x1^{2} + 12288x2^{3} - 19296x1x2^{2} + 7344x1^{2}x2 - 1072x1^{3} + 14346x2^{4} - 23616x1x2^{3} + 7776x1^{2}x2^{2} + 5784x1^{3}x2 - 2454x1^{4} + 1944x2^{5} - 11880x1x2^{4} + 5040x1^{2}x2^{3} + 9840x1^{3}x2^{2} - 7680x1^{4}x2 + 1344x1^{5} - 4428x2^{6} - 1188x1x2^{5} + 8730x1^{2}x2^{4} + 1240x1^{3}x2^{3} - 5370x1^{4}x2^{2} - 168x1^{5}x2 + 952x1^{6} - 648x2^{7} + 1944x1x2^{6} + 3672x1^{2}x2^{5} - 3480x1^{3}x2^{4} - 4080x1^{4}x2^{3} + 2592x1^{5}x2^{2} + 1344x1^{6}x2 - 768x1^{7} + 729x2^{8} + 972x1x2^{7} - 1458x1^{2}x2^{6} - 1836x1^{3}x2^{5} + 1305x1^{4}x2^{4} + 1224x1^{5}x2^{3} - 648x1^{6}x2^{2} - 288x1^{7}x2 + 144x1^{8} \]
We need to pick an SDP solver, see here for a list of the available choices. We use SOSModel instead of Model to be able to use the >= syntax for Sum-of-Squares constraints.
using SumOfSquares
using CSDP
solver = optimizer_with_attributes(CSDP.Optimizer, MOI.Silent() => true)
model = SOSModel(solver);We create the decision variable $\gamma$ that will be the lower bound to the Goldstein-Price function. We maximize it to have the highest possible lower bound.
@variable(model, γ)
@objective(model, Max, γ)$ γ $
We constrain $\gamma$ to be a lower bound with the following constraint that ensures that $f(x_1, x_2) \ge \gamma$ for all $x_1, x_2$.
@constraint(model, f >= γ)
JuMP.optimize!(model)We verify that the solver has found a feasible solution:
JuMP.primal_status(model)NEARLY_FEASIBLE_POINT::ResultStatusCode = 2We can now obtain the lower bound either with value(γ) or objective_value(model):
objective_value(model)2.999991053480265This page was generated using Literate.jl.